__author__ = 'st316'
'''
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
'''


class Solution:
    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudoku(self, board):
        for i in xrange(9):  # the rows
            a = set()
            for j in xrange(9):
                if board[i][j] == '.':
                    pass
                else:
                    if board[i][j] in a:
                        return False
                    else:
                        a.add(board[i][j])

        for i in xrange(9):  # the columns
            a = set()
            for j in xrange(9):
                if board[j][i] == '.':
                    pass
                else:
                    if board[j][i] in a:
                        return False
                    else:
                        a.add(board[j][i])

        x, y = 0, 0
        while x < 7 and y < 7:
            a = set()
            for i in xrange(x, x + 3):  # the sub-boxes
                for j in xrange(y, y + 3):
                    if board[i][j] == '.':
                        pass
                    else:
                        if board[i][j] in a:
                            return False
                        else:
                            a.add(board[i][j])
            if x < 6:
                x += 3
            else:
                x = 0
                y += 3

        return True

    # @param board, a 9x9 2D array
    # @return a boolean
    def isValidSudokuX(self, board):
        rows = [[False]*9 for __ in xrange(9)]
        cols = [[False]*9 for __ in xrange(9)]
        blocks = [[False]*9 for __ in xrange(9)]

        for i in xrange(9):
            for j in xrange(9):
                if board[i][j] == '.':
                    continue
                c = ord(board[i][j]) - ord('1')
                if rows[i][c] or cols[j][c] or blocks[i - i % 3 + j / 3][c]:
                    return False
                rows[i][c] = cols[j][c] = blocks[i - i % 3 + j / 3][c] = True
        return True


if __name__ == '__main__':
    s = Solution()
    print s.isValidSudokuX(
        [".87654321", "2........", "3........", "4........", "5........", "6........", "7........", "8........",
         "9........",
        ])